package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 78. 子集
 * @date 2024/12/22 11:44
 */
public class E78 {

    /**
     * <h3>方法一：回溯，更清晰</h3>
     * @param nums 数组
     * @return 所有子集
     */
    public List<List<Integer>> subsets1(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++)
            dfs(result, nums, new LinkedList<>(), i, 0);
        return result;
    }

    /**
     * 回溯
     * @param result 结果集
     * @param nums 数组
     * @param currCombine 当前子集
     * @param size 子集大小
     * @param start 开始位置
     */
    private void dfs(
            List<List<Integer>> result,
            int[] nums,
            LinkedList<Integer> currCombine,
            int size,
            int start) {
        // 1. 递归结束条件
        if (size == 0) {
            result.add(new ArrayList<>(currCombine));
            return;
        }
        // 2. 尝试当前位置的所有可能
        for (int i = start; i < nums.length; i++) {
            // 2.1 剪枝
            if (nums.length - start < size) break;
            // 2.2 尝试当前位置
            currCombine.push(nums[i]);
            dfs(result, nums, currCombine, size - 1, i + 1); // i+1！
            currCombine.pop();
        }
    }

    /**
     * <h3>方法二：回溯，更简洁</h3>
     * @param nums 数组
     * @return 所有子集
     */
    public List<List<Integer>> subsets2(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, nums, new LinkedList<>(), 0);
        return result;
    }

    /**
     * 回溯
     * @param result 结果集
     * @param nums 数组
     * @param currCombine 当前子集
     * @param start 开始位置
     */
    private void dfs(List<List<Integer>> result, int[] nums, LinkedList<Integer> currCombine, int start) {
        result.add(new ArrayList<>(currCombine));
        for (int i = start; i < nums.length; i++) {
            currCombine.push(nums[i]);
            dfs(result, nums, currCombine, i + 1);
            currCombine.pop();
        }
    }
}
